package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/21 23:22
 * @description：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 */
public class 搜索旋转排序数组 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {
        public int search(int[] nums, int target) {
            int len = nums.length;
            int l = 0;
            int r = len - 1;
            int mid;
            //找到数组中的最小值
            while (l < r) {
                mid = l + r >> 1;
                if (nums[mid] <= nums[r]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            //根据最小值的位置重新划分区间
            if (nums[l] <= target && nums[len - 1] >= target) {
                r = len - 1;
            } else {
                r = l - 1;
                l = 0;
            }
            while (l < r) {
                mid = l + r >> 1;
                if (nums[mid] >= target) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return nums[l] == target ? l : -1;
        }
    }

}
